#include "BinaryTree.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}


int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	if (leftHeight > rightHeight)
	{
		return leftHeight + 1;
	}
	else
	{
		return rightHeight + 1;
	}

	/*return root == NULL ? 0 : 
		(TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1);*/
}

int TreeKLevel(BTNode* root, int k)
{
	if (root == NULL) 
		return 0;
	if (k == 1) 
		return 1;
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);

}

BTNode* BinaryFindTree(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* lret = BinaryFindTree(root->left, x);
	if (lret)
		return lret;
	BTNode* rret = BinaryFindTree(root->right, x);
	if (rret)
		return rret;

	return NULL;
}

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* p = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", p->data);
		if (p->left)
			QueuePush(&q, p->left);
		if (p->right)
			QueuePush(&q, p->right);
	}
	QueueDestroy(&q);
	printf("\n");
}

//int TreeComplete(BTNode* root)
//{
//	int size = TreeSize(root);
//	char* a = (char*)malloc(sizeof(char) * size);
//	if (a == NULL)
//	{
//		perror("malloc fail");
//		return 0;
//	}
//	int i = 0;
//	Queue q;
//	QueueInit(&q);
//	QueuePush(&q, root);
//	while (!QueueEmpty(&q))
//	{
//		BTNode* p = QueueFront(&q);
//		QueuePop(&q);
//		if(p)
//			a[i++] = 'T';
//		else
//		{
//			a[i++] = 'N';
//		}
//		if (p)
//		{
//			QueuePush(&q, p->left);
//			QueuePush(&q, p->right);
//		}
//	}
//	QueueDestroy(&q);
//
//	int cur = 0;
//	while (a[cur]=='T')
//	{
//		cur++;
//	}
//
//	for (cur; cur < size; cur++)
//	{
//		if (a[cur] == 'T')
//		{
//			printf("Is Not CompleteTree\n");
//			return 0;
//
//		}
//	}
//	printf("Is CompleteTree\n");
//	return 1;
//}

//判断是否为完全二叉树
//逻辑类似于层序遍历，如果是完全二叉树的话，非空节点一定是连续的
bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if(root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* p = QueueFront(&q);
		QueuePop(&q);
		if (p == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, p->left);
			QueuePush(&q, p->right);
		}
	}

	//判断是否为完全二叉树，如果有非空节点，就证明不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* p = QueueFront(&q);
		QueuePop(&q);
		if (p)
		{
			printf("IS NOT COMPLETE\n");
			QueueDestroy(&q);
			return false;
		}
	}

	printf("IS COMPLETE\n");
	QueueDestroy(&q);
	return true;
}


void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}